package 链表;

/**
 * 138. 随机链表的复制
 *
 * 思路： 先基于原链表进行复制，将复制的节点拼接到被复制的节点之后， 等完成随机指针的指向后，再分离位两个链表
    解法：
    1：遍历原链表，复制每个节点并插入到原节点后面：
        对于原链表中的每个节点，创建一个新节点，并将其插入到原节点和原节点的下一个节点之间。这样，原链表和新链表就交织在一起。
    2：设置新节点的 random 指针：
        由于新节点是插入在原节点后面的，所以新节点的 random 指针应该指向原节点的 random 指针的下一个节点（即原节点的 random 指针指向的节点的复制节点）。
    3：分离新链表和原链表;
 */
public class L_138 {

    public Node copyRandomList(Node head) {
        if(head == null){
            return head;
        }
        // 第一步：复制原有节点，并将新节点插入到原节点的后面
        Node cur = head;
        while (cur != null){
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            // 持续遍历下一个原有节点
            cur = newNode.next;
        }
        // 第二步：设计新节点的 random 指针, 新节点的Random指针就指向原老节点的下一位即可
        cur = head;
        while (cur != null){
            if(cur.random != null){
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        // 第三步: 分离新链表和原链表
        Node newNode = head.next;
        cur = head;
        while (cur != null){
            // 新链表的起点
            Node temp = cur.next;
            // 原链表的拆分
            cur.next = temp.next;
            // 新链表的拆分
            if(temp.next != null){
                temp.next = temp.next.next;
            }
            cur = cur.next;
        }
        return newNode;
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
}
